import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Oj {
    /** Oj ---- 面试题 17.14. 最小K个数
     设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
     */
    public static int[] smallestK(int[] arr, int k) { // 1
        Arrays.sort(arr);
        int[] tmp = new int[k];
        for(int i = 0; i < k; i++) {
            tmp[i] = arr[i];
        }
        return tmp;
    }
    //时间复杂度 O（ N + K*log(n) ）
    public static int[] smallestK2(int[] arr, int k) { // 2
        //1.建立一个小根堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        // 2.取出数组当中的每个元素，存放在小根堆当中
        for (int i = 0; i < arr.length; i++) { //n个元素向上调整，时间复杂度O(n)
            minHeap.offer(arr[i]);
        }
        // 3.弹出k个元素，存放在数组当中，返回即可
        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) { //K个元素就要调整K次，O(K*log(n))
            tmp[i] = minHeap.poll();
        }
        return tmp;
    }
    //时间复杂度 O（ N*log(k) ）
    // ****************   TopK问题  *******************
    public static int[] smallestK3(int[] arr, int k) { // 3
        if(arr == null || k == 0) {
            return new int[0];
        }
        //因为默认是小根堆，所以建立大根堆要传入比较器自己定义
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        }); //匿名内部类
        for (int i = 0; i < arr.length; i++) {
            if(maxHeap.size() < k) { //在大根堆放满k个元素
                maxHeap.offer(arr[i]);
            }else {
                //当前数组的元素是arr[i]
                int val = maxHeap.peek();
                if(val > arr[i]) {
                    //弹出大的,放进小的
                    maxHeap.poll();
                    maxHeap.offer(arr[i]);
                }
            }
        }
        int[] tmp = new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i] = maxHeap.poll();
        }
        return tmp;
    }
    public static void main(String[] args) {
        int[] array = {1, 5, 2, 9, 8, 20, 18};
        smallestK2(array,3);
        int[] tmp = smallestK3(array,3);
        System.out.println(Arrays.toString(tmp));
    }
}
